package code.mySpecializedTraining;

import utils.TreeNode;

import java.util.*;

/**
 * @author 26029
 * @date 2025/4/16
 * @description
 */
public class Tree {
    // 144. 二叉树的前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode node = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                list.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return list;
    }

    // 94. 二叉树的中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode node = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            list.add(node.val);
            node = node.right;
        }
        return list;
    }

    // 145. 二叉树的后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode node = root, prev = null;
        Deque<TreeNode> stack = new LinkedList<>();
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                prev = node;
                node = node.left;
            }
            node = stack.pop();
            // 右面遍历过了
            if (node.right == null || prev == node.right) {
                list.add(node.val);
                prev = node;
                node = null;
            } else {
                stack.push(node);
                node = node.right;
            }
        }
        return list;
    }

    // 102. 二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null)
            return lists;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode n = queue.poll();
                list.add(n.val);
                if (n.left != null)
                    queue.offer(n.left);
                if (n.right != null)
                    queue.offer(n.right);
            }
            lists.add(list);
        }
        return lists;
    }

    // 226. 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return null;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;

        return root;
    }

    // 101. 对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        return isGood(root.left, root.right);
    }

    private boolean isGood(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null)
            return true;
        if (node1 == null || node2 == null)
            return false;
        if (node1.val != node2.val)
            return false;
        boolean lr = isGood(node1.left, node2.right);
        boolean rl = isGood(node1.right, node2.left);
        return lr && rl;
    }

    // 104. 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }

    public int maxDepth_(TreeNode root) {
        // 层次遍历
        int depth = 0;
        if (root == null)
            return depth;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
        }

        return depth;
    }

    // 111. 二叉树的最小深度
    public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
        if (root.left == null && root.right == null)
            return 1;
        if (root.left == null)
            return minDepth(root.right) + 1;
        if (root.right == null)
            return minDepth(root.left) + 1;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return Math.min(left, right) + 1;
    }

    public int minDepth_(TreeNode root) {
        if (root == null)
            return 0;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;
        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null)
                    return level;
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
        }
        return level;
    }

    // 222. 完全二叉树的节点个数
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        // get depth
        int depth = 0;
        TreeNode nodeToDepth = root;
        while (nodeToDepth != null) {
            depth++;
            nodeToDepth = nodeToDepth.left;
        }
        // node num of layer[1, depth - 1] is 2^(depth - 1) - 1
        int nodeNum = (int) (Math.pow(2, depth - 1) - 1);
        // figure out the last layer with binary search : num possibly in [2^(depth-1), 2^depth - 1]
        int start = (int) Math.pow(2, depth - 1), end = (int) Math.pow(2, depth) - 1;
        while (start < end) {
            int mid = end + (start - end) / 2;
            // get how to go mid
            TreeNode find = root;
            // if the last layer is depth 3, then from 4 to 7, 100 to 111, use the last two digit 00-11 represent left and right
            for (int i = depth - 2; i >= 0; i--) {
                int left0right1 = (mid >> i) & 1;
                if (left0right1 == 0)
                    find = find.left;
                else
                    find = find.right;
            }
            if (find == null)
                end = mid - 1;
            else
                start = mid;
        }
        nodeNum += start - (int) Math.pow(2, depth - 1) + 1;
        return nodeNum;
    }

    // 110. 平衡二叉树
    boolean isBalancedTree = true;

    public boolean isBalanced(TreeNode root) {
        int height = isBalancedGetHeight(root);
        return isBalancedTree;
    }

    private int isBalancedGetHeight(TreeNode root) {
        if (root == null)
            return 0;
        int left = isBalancedGetHeight(root.left);
        int right = isBalancedGetHeight(root.right);
        if (Math.abs(left - right) > 1)
            isBalancedTree = false;
        return Math.max(left, right) + 1;
    }

    // 257. 二叉树的所有路径
    public List<String> binaryTreePaths(TreeNode root) {
        // 节点数在 [1, 1000] 范围内
        List<String> stringList = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        sb.append(root.val);
        binaryTreePathsDFS(root, stringList, sb);
        return stringList;
    }

    private void binaryTreePathsDFS(TreeNode root, List<String> stringList, StringBuilder sb) {
        if (root.right == null && root.left == null) {
            stringList.add(sb.toString());
            return;
        }
        if (root.left != null) {
            sb.append("->");
            sb.append(root.left.val);
            binaryTreePathsDFS(root.left, stringList, sb);
            int len = String.valueOf(root.left.val).length() + 2;
            sb.delete(sb.length() - len, sb.length());
        }
        if (root.right != null) {
            sb.append("->");
            sb.append(root.right.val);
            binaryTreePathsDFS(root.right, stringList, sb);
            int len = String.valueOf(root.right.val).length() + 2;
            sb.delete(sb.length() - len, sb.length());
        }
    }

    // 404. 左叶子之和
    public int sumOfLeftLeaves(TreeNode root) {
        // 节点数在 [1, 1000] 范围内
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int leftNum = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null && node.left.left == null && node.left.right == null)
                leftNum += node.left.val;
            else if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
        return leftNum;
    }

    // 513. 找树左下角的值
    public int findBottomLeftValue(TreeNode root) {
        // 二叉树的节点个数的范围是 [1,10^4]
        int ans = 0;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == 0)
                    ans = node.val;
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
        }
        return ans;
    }

    // 112. 路径总和
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null)
            return false;
        hasPathDFS(root, targetSum - root.val);
        return isOK;
    }

    boolean isOK = false;

    private void hasPathDFS(TreeNode node, int targetSum) {
        if (node.left == null && node.right == null && targetSum == 0) {
            isOK = true;
            return;
        }
        if (node.left != null)
            hasPathDFS(node.left, targetSum - node.left.val);
        if (node.right != null)
            hasPathDFS(node.right, targetSum - node.right.val);
    }

    // 106. 从中序与后序遍历序列构造二叉树
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int len = inorder.length;
        Map<Integer, Integer> inorderPos = new HashMap<>();
        for (int i = 0; i < len; i++) {
            inorderPos.put(inorder[i], i);
        }
        return build(inorder, postorder, 0, len - 1, 0, len - 1, inorderPos);
    }

    private TreeNode build(int[] inorder, int[] postorder, int inBegin, int inEnd, int postBegin, int postEnd, Map<Integer, Integer> inorderPos) {
        if (inBegin > inEnd || postBegin > postEnd)
            return null;
        TreeNode node = new TreeNode();
        node.val = postorder[postEnd];
        int inMid = inorderPos.get(postorder[postEnd]);
        int leftNum = inMid - inBegin;
        // inorder : [inBegin, inMid - 1] inMid [inMid + 1, inEnd]
        // postorder : [postBegin, postBegin + leftNum - 1] [postBegin + leftNum, postEnd - 1] postEnd
        node.left = build(inorder, postorder, inBegin, inMid - 1, postBegin, postBegin + leftNum - 1, inorderPos);
        node.right = build(inorder, postorder, inMid + 1, inEnd, postBegin + leftNum, postEnd - 1, inorderPos);
        return node;
    }

    // 654. 最大二叉树
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int len = nums.length;
        return constructMBT(nums, 0, len - 1);
    }

    private TreeNode constructMBT(int[] nums, int begin, int end) {
        if (begin > end)
            return null;
        int maxPos = begin, max = nums[begin];
        for (int i = begin + 1; i <= end; i++) {
            if (nums[i] > nums[maxPos]) {
                max = nums[i];
                maxPos = i;
            }
        }
        TreeNode node = new TreeNode();
        node.val = max;
        node.left = constructMBT(nums, begin, maxPos - 1);
        node.right = constructMBT(nums, maxPos + 1, end);
        return node;
    }

    // 617. 合并二叉树
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null)
            return null;
        TreeNode node = new TreeNode(0);
        if (root1 != null)
            node.val += root1.val;
        if (root2 != null)
            node.val += root2.val;
        node.left = mergeTrees(root1 == null ? null : root1.left, root2 == null ? null : root2.left);
        node.right = mergeTrees(root1 == null ? null : root1.right, root2 == null ? null : root2.right);
        return node;
    }

    // 700. 二叉搜索树中的搜索
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null)
            return null;
        if (root.val == val)
            return root;
        return val > root.val ? searchBST(root.right, val) : searchBST(root.left, val);
    }

    // 98. 验证二叉搜索树
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        boolean isFirst = true;
        int last = 0;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();

            if (isFirst)
                isFirst = false;
            else if (node.val <= last)
                return false;

            last = node.val;
            node = node.right;
        }
        return true;
    }

    // 501. 二叉搜索树中的众数
    private List<Integer> ans = new ArrayList<>();
    private int maxCount = 0, nowCount = 0;
    private int num = 0;

    public int[] findMode(TreeNode root) {
        // 没有额外空间的morris遍历：前驱节点
        TreeNode node = root, prev = null;
        while (node != null) {
            // 如果当前节点没有左孩子，遍历自身，转向右孩子
            if (node.left == null) {
                handle(node.val);
                node = node.right;
                continue;
            }
            // 如果有左孩子，找到当前节点的前驱
            prev = node.left;
            while (prev.right != null && prev.right != node) {
                prev = prev.right;
            }
            // 如果前驱下一个没有，说明没访问过，加上连接，访问左子
            if (prev.right == null) {
                prev.right = node;
                node = node.left;
            } else { // 如果前驱的下一个就是node，说明访问过前驱，断掉联系，访问node自身，转向右面
                prev.right = null;
                handle(node.val);
                node = node.right;
            }
        }
        int[] a = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            a[i] = ans.get(i);
        }
        return a;
    }

    public void handle(int val) {
        if (val == num) {
            nowCount++;
        } else {
            nowCount = 1;
            num = val;
        }
        if (nowCount >= maxCount) {
            if (nowCount > maxCount) {
                ans.clear();
                maxCount = nowCount;
            }
            ans.add(val);
        }
    }

    // 236. 二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null)
            return root;
        if (left == null)
            return right;
        else
            return left;
    }

    // 235. 二叉搜索树的最近公共祖先
    public TreeNode lowestCommonAncestor_bst(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        int a1 = p.val, a2 = q.val;
        int left = Math.min(a1, a2), right = Math.max(a1, a2);
        if (left <= root.val && root.val <= right)
            return root;
        if (root.val < left)
            return lowestCommonAncestor_bst(root.right, p, q);
        else
            return lowestCommonAncestor_bst(root.left, p, q);
    }

    // 701. 二叉搜索树中的插入操作
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null)
            return new TreeNode(val);
        TreeNode node = root;
        TreeNode prev = null;
        while (node != null) {
            prev = node;
            if (node.val > val)
                node = node.left;
            else
                node = node.right;
        }
        if (prev.val > val)
            prev.left = new TreeNode(val);
        else
            prev.right = new TreeNode(val);
        return root;
    }

    // 450. 删除二叉搜索树中的节点
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return null;
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        } else {
            // 删除root
            if (root.left == null)
                return root.right;
            if (root.right == null)
                return root.left;
            // 找到要删的节点的右面的最左节点
            TreeNode rightMin = root.right;
            TreeNode rightMinPrev = root;
            while (rightMin.left != null) {
                rightMinPrev = rightMin;
                rightMin = rightMin.left;
            }
            // 如果右节点没有左子了(上面的循环没进去),直接返回右子即可,否则把右节点最小左子拿上来
            if (rightMinPrev != root) {
                rightMinPrev.left = rightMin.right;
                rightMin.right = root.right;
            }
            rightMin.left = root.left;
            return rightMin;
        }
    }

    // 669. 修剪二叉搜索树
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null)
            return null;
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }

    // 108. 将有序数组转换为二叉搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        return getBST(nums, 0, nums.length - 1);
    }

    private TreeNode getBST(int[] nums, int start, int end) {
        if (start > end)
            return null;
        int mid = (end - start) / 2 + start;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = getBST(nums, start, mid - 1);
        node.right = getBST(nums, mid + 1, end);
        return node;
    }

    // 538. 把二叉搜索树转换为累加树
    public TreeNode convertBST(TreeNode root) {
        int count = 0;
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.right;
            }
            node = stack.pop();
            node.val += count;
            count = node.val;
            node = node.left;
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.fromArray(new int[]{1, 2, 3, 4, 5, 6});
        Tree t = new Tree();
        int i = t.countNodes(null);
        System.out.println(i);
    }
}
